By using SIAM Journals Online you agree to abide by the
Terms and Conditions of Use.

©  SIAM

 

SIAM Journal on Computing

Table of Contents
Search This Issue
Volume 36, Issue 5, pp. 1231-1511

Please Note: Electronic articles are available well in advance of the printed articles.

What Article options are available ?   View Cart   

Deterministic Extractors for Bit-Fixing Sources and Exposure-Resilient Cryptography

Jesse Kamp and David Zuckerman

pp. 1231-1247

BibTeX  Abstract Full Text:  PDF

Linear Upper Bounds for Random Walk on Small Density Random $3$-CNFs

Mikhail Alekhnovich and Eli Ben-Sasson

pp. 1248-1263

BibTeX  Abstract Full Text:  PDF

The Complexity of Computing the Size of an Interval

Lane A. Hemaspaandra, Christopher M. Homan, Sven Kosub, and Klaus W. Wagner

pp. 1264-1300

BibTeX  Abstract Full Text:  PDF

Chosen-Ciphertext Security from Identity-Based Encryption

Dan Boneh, Ran Canetti, Shai Halevi, and Jonathan Katz

pp. 1301-1328

BibTeX  Abstract Full Text:  PDF

A Deterministic Algorithm for Finding All Minimum $k$-Way Cuts

Yoko Kamidoi, Noriyoshi Yoshida, and Hiroshi Nagamochi

pp. 1329-1341

BibTeX  Abstract Full Text:  PDF

Online Conflict-Free Coloring for Intervals

Ke Chen, Amos Fiat, Haim Kaplan, Meital Levy, Jirí Matoušek, Elchanan Mossel, János Pach, Micha Sharir, Shakhar Smorodinsky, Uli Wagner, and Emo Welzl

pp. 1342-1359

BibTeX  Abstract Full Text:  PDF

Improved Combinatorial Group Testing Algorithms for Real-World Problem Sizes

David Eppstein, Michael T. Goodrich, and Daniel S. Hirschberg

pp. 1360-1375

BibTeX  Abstract Full Text:  PDF

The Hardness of Metric Labeling

Julia Chuzhoy and Joseph (Seffi) Naor

pp. 1376-1386

BibTeX  Abstract Full Text:  PDF

Pseudorandom Bits for Constant-Depth Circuits with Few Arbitrary Symmetric Gates

Emanuele Viola

pp. 1387-1403

BibTeX  Abstract Full Text:  PDF

Locally Decodable Codes with Two Queries and Polynomial Identity Testing for Depth 3 Circuits

Zeev Dvir and Amir Shpilka

pp. 1404-1434

BibTeX  Abstract Full Text:  PDF

The Probabilistic Relationship Between the Assignment and Asymmetric Traveling Salesman Problems

Alan Frieze and Gregory B. Sorkin

pp. 1435-1452

BibTeX  Abstract Full Text:  PDF

The Wake-Up Problem in MultiHop Radio Networks

Marek Chrobak, Leszek Gasieniec, and Dariusz R. Kowalski

pp. 1453-1471

BibTeX  Abstract Full Text:  PDF

Quantum and Classical Strong Direct Product Theorems and Optimal Time-Space Tradeoffs

Hartmut Klauck, Robert Špalek, and Ronald de Wolf

pp. 1472-1493

BibTeX  Abstract Full Text:  PDF

Integrality Ratio for Group Steiner Trees and Directed Steiner Trees

Eran Halperin, Guy Kortsarz, Robert Krauthgamer, Aravind Srinivasan, and Nan Wang

pp. 1494-1511

BibTeX  Abstract Full Text:  PDF